#pragma once
#include<iostream>
using namespace std;

template<class k, class v>
struct AvlTreemenber
{
public:
	AvlTreemenber(pair<k, v> kv)
		:_left(nullptr)
		, _right(nullptr)
		,_parend(nullptr)
		, _kv(kv)
		,_bf(0)
	{

	}
	AvlTreemenber<k, v>* _left;
	AvlTreemenber<k, v>* _right;
	AvlTreemenber<k, v>* _parend;

	pair<k, v> _kv;
	int _bf;  // balance


};

template<class k, class v>
class AvlTree
{
public:
	typedef AvlTreemenber<k, v> node;
	bool insert(const k& key)
	{
		if (_root == nullptr)
		{
			_root = new node(key);
			return true;
		}

		node* cut = _root;
		node* parent = _root;
		while (cut)
		{
			if (key == cut->_kv.first)
			{
				return false;
			}
			if (key < cut->_kv.first)
			{
				parent = cut;
				cut = cut->_left;
			}
			else if (key > cut->_kv.first)
			{
				parent = cut;
				cut = cut->_right;
			}
			else
			{
				return false;
			}
		}
		cut = new node(key);
		if (parent->_kv.first > key)
		{
			parent->_left = cut;
		}
		if (parent->_kv.first < key)
		{
			parent->_right = cut;
		}
		return true;
	}
private:
	node* _root = nullptr;
};